package run.siyuan.jdk.漫画算法.树;

import cn.hutool.core.collection.ListUtil;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName BinaryTree
 * @Description TODO 链表实现简单的二叉树
 * @Author siyuan
 * @Date 2023/4/8 16:14
 */
public class LinkedBinaryTree {

    private TreeNode rootNode;
    private int size;

    public static void main(String[] args) {
        LinkedList<Integer> list = ListUtil.toLinkedList(1, 2, 3, null, null, 4, null, null, 5, null, 6);
        TreeNode node = createTreeNode(list);
        System.out.println("递归前序遍历：");
        preShow(node);
        System.out.println("栈前序遍历：");
        preStackShow(node);
        System.out.println("递归中序遍历：");
        inShow(node);
        System.out.println("栈中序遍历：");
        inStackShow(node);
        System.out.println("递归后序遍历：");
        postShow(node);
        System.out.println("栈后序遍历：");
        postStackShow(node);

    }

    /**
     * @Desc 创建二叉树，通过null 值来控制二叉树的层级，否测元素会一直在左子树上
     * @Date 下午11:14 2025/1/9
     **/
    public static TreeNode createTreeNode(LinkedList<Integer> inputList) {
        if (inputList == null || inputList.size() == 0) {
            return null;
        }
        // 从列表中一出并返回第一个元素
        Integer data = inputList.removeFirst();
        TreeNode treeNode = null;
        if (data != null) {
            treeNode = new TreeNode(data);
            treeNode.leftNode = createTreeNode(inputList);
            treeNode.rightNode = createTreeNode(inputList);
        }
        return treeNode;

    }

    /**
     * 前序遍历：根节点、左子树、右子树
     */
    public static void preShow(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preShow(node.leftNode);
        preShow(node.rightNode);

    }

    /**
     * 中序遍历：左子树、根节点、右子树
     */
    public static void inShow(TreeNode node) {
        if (node == null) {
            return;
        }
        inShow(node.leftNode);
        System.out.println(node.data);
        inShow(node.rightNode);

    }

    /**
     * 后序遍历：左子树、右子树、根节点
     */
    public static void postShow(TreeNode node) {
        if (node == null) {
            return;
        }
        postShow(node.leftNode);
        postShow(node.rightNode);
        System.out.println(node.data);

    }


    /**
     * @Desc 利用队列实现 层级遍历：左子树、右子树、根节点
     * @Date 下午11:29 2025/1/9
     **/
    public static void levelShow(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        // 元素入队
        queue.offer(node);
        while (!queue.isEmpty()) {
            // 出队
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.data);
            if (treeNode.leftNode != null) {
                queue.offer(treeNode.leftNode);
            }
            if (treeNode.rightNode != null) {
                queue.offer(treeNode.rightNode);
            }
        }

    }

    /**
     * @Desc 利用栈实现 前序遍历：根节点、左子树、右子树
     * @Date 下午11:29 2025/1/9
     **/
    public static void preStackShow(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 开始遍历节点
        while (node != null || !stack.isEmpty()) {
            // 遍历根、左节点，并入栈，为空时结束
            while (node != null) {
                System.out.println(node.data);
                stack.push(node);
                node = node.leftNode;
            }
            // 左节点遍历完成，切换至右节点
            if (!stack.isEmpty()){
                node = stack.pop();
                node = node.rightNode;
            }
        }
    }

    /**
     * @Desc 利用栈实现 中序遍历：左子树、根节点、右子树
     * @Date 下午11:29 2025/1/9
     **/
    public static void inStackShow(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 开始遍历节点
        while (node != null || !stack.isEmpty()) {
            // 遍历左节点
            while (node != null) {
                stack.push(node);
                node = node.leftNode;
            }
            // 左节点遍历完成，切换至右节点
            if (!stack.isEmpty()){
                node = stack.pop();
                System.out.println(node.data);
                node = node.rightNode;
            }
        }
    }

    /**
     * @Desc 利用栈实现 后序遍历：左子树、右子树、根节点
     * @Date 下午11:29 2025/1/9
     **/
    public static void postStackShow(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = null;
        // 开始遍历节点
        while (node != null || !stack.isEmpty()) {
            // 遍历左节点
            while (node != null) {
                stack.push(node);
                node = node.leftNode;
            }
            // 左节点遍历完成，切换至右节点
            if (!stack.isEmpty()){
                TreeNode peek = stack.peek();
                if (peek.rightNode != null && peek.rightNode != temp) {
                    node = peek.rightNode;
                }else {
                    System.out.println(peek.data);
                    temp = stack.pop();
                    node = null;
                }
            }
        }
    }


    public static class TreeNode {
        private int data;

        private TreeNode leftNode;
        private TreeNode rightNode;

        public TreeNode(int data) {
            this.data = data;
        }
    }

}
